package leetcode.Leetcode41;

class Solution {
    public int firstMissingPositive(int[] nums) {
        //若全部连续，则最小为N+1
        //全部<=0的数都换成N+1
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (nums[i] <= 0) {
                nums[i] = len + 1;
            }
            /*else {
                nums[i] = -nums[i];
            }*/
        }
        //然后遍历每个数，对于每个数，如果它在1...n，则表示其出现，将nums[此数大小]加上负值。注意这里加绝对值是为了防止重复标记
        for (int i = 0; i < len; i++) {
            int num = Math.abs(nums[i]);
            if (num <= len) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        //最后找到nums[i]为正的，返回i+1即可，否则返回n+1
        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                return i+1;
            }
        }
        return len+1;
    }

    public static void main(String[] args){
        Solution solution = new Solution();
        int s = solution.firstMissingPositive(new int[]{3,4,-1,1});
        System.out.println(s);
    }
}